class Solution {
public:
  int coinChange(vector<int>& coins, int amount) {

    int n = coins.size();
    if(n == 0){
      return -1;
    }

    int dp[amount + 1];
    fill(dp, dp + amount + 1, amount + 1);
    dp[0] = 0;
    for(int i = 1; i <= amount; ++i){
      for(int j = 0; j < n; ++j){
        if(i - coins.at(j) >= 0){
          // dp[i]有两种实现的方式，
          // 一种是包含当前的coins[j],那么剩余钱就是 i-coins[j],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
          // 另一种就是不包含，要兑换的硬币数是dp[i]
          dp[i] = min(dp[i - coins.at(j)] + 1, dp[i]);
        }
      }
    }

    return dp[amount] == amount + 1 ? -1 : dp[amount];

  }
};